package com.itheima.leetcode.od.b.greedy;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * (A卷,200分)- 连接器问题（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 有一组区间[a0，b0]，[a1，b1]，…（a，b表示起点，终点），区间有可能重叠、相邻，重叠或相邻则可以合并为更大的区间；
 * <p>
 * 给定一组连接器[x1，x2，x3，…]（x表示连接器的最大可连接长度，即x>=gap），可用于将分离的区间连接起来，但两个分离区间之间只能使用1个连接器；
 * <p>
 * 请编程实现使用连接器后，最少的区间数结果。
 * <p>
 * 区间数量<10000，a,b均 <=10000
 * 连接器梳理<10000；x <= 10000
 * <p>
 * 输入描述
 * <p>
 * 区间组：[1,10],[15,20],[18,30],[33，40]
 * 连接器组：[5,4,3,2]
 * <p>
 * 输出描述
 * <p>
 * 1
 * <p>
 * 说明：
 * <p>
 * 合并后：[1,10],[15,30],[33,40]，使用5, 3两个连接器连接后只剩下 [1, 40]。
 * <p>
 * 用例
 * <p>
 * 输入	[1,10],[15,20],[18,30],[33,40]
 * <p>
 * [5,4,3,2]
 * <p>
 * 输出	1
 * <p>
 * 说明	合并后：[1,10], [15,30], [33,40]，使用5, 3两个连接器连接后只剩下[1,40]。
 * <p>
 * 输入	[1,2],[3,5],[7,10],[15,20],[30,100]
 * <p>
 * [5,4,3,2,1]
 * <p>
 * 输出	2
 * <p>
 * 说明	无重叠和相邻，使用1，2，5三个连接器连接后只剩下[1,20]，[30,100]
 * <p>
 * 题目解析
 * <p>
 * 我的解题思路如下：
 * <p>
 * 首先将第一行输入的区间ranges，按照起点值升序排序。然后进行区间合并。
 * <p>
 * 区间合并的逻辑如下，创建一个辅助数组mergeRanges，将ranges[0]从ranges中出队，并加入mergeRanges，作为其初始值。
 * <p>
 * 然后，循环遍历ranges中剩余区间，
 * <p>
 * 如果ranges[i]和mergeRanges.at(-1)栈顶元素可以合并，则将mergeRanges栈顶元素弹出，并加入合并后区间。
 * 如果ranges[i]和mergeRanges.at(-1)栈顶元素无法合并，则先计算ranges[i]的终点和栈顶mergeRanges.at(-1)的起点的差值diff，加入diffs数组中，然后将ranges[i]压入mergeRanges
 * 以上逻辑运行完后，我们就得到了一个diffs数组。diffs保存的是合并后相邻区间之间的空隙大小。
 * <p>
 * 现在想要最少的区间数，即我们应该尽量让连接器不要浪费，即最好找到一个空隙长度相等的连接器，这样就可以防止一个很长的连接器来连一个很短的空隙，导致后面遇到很长的空隙时，没有适合的连接器使用。
 * <p>
 * 我们将diffs数组降序排序，将第二行输入的连接器connects数组降序排序。
 * <p>
 * 然后不停的弹出connects栈顶元素，即最小长度的连接器，来对比diffs数组栈顶元素，即最短的空隙，如果最小长度的连接器 可以满足 最短的空隙，则将diffs栈顶元素弹出，否则不弹出，继续找下一个连接器。
 * <p>
 * 最终，diffs数组长度 + 1 就是区间数，因为两个区间有一个空隙，因此空隙个数+1就是区间个数。
 */
public class ConnectorIssues {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        String f = sc.nextLine();
        Integer[][] ranges =
                Arrays.stream(f.substring(1, f.length() - 1).split("],\\["))
                        .map(
                                str -> Arrays.stream(str.split(",")).map(Integer::parseInt).toArray(Integer[]::new))
                        .toArray(Integer[][]::new);

        String s = sc.nextLine();
        List<Integer> connects =
                s.length() == 2
                        ? new LinkedList<>()
                        : Arrays.stream(s.substring(1, s.length() - 1).split(","))
                        .map(Integer::parseInt)
                        .collect(Collectors.toList());*/

        String f = "[1,10],[15,20],[18,30],[33,40]";
        Integer[][] ranges =
                Arrays.stream(f.substring(1, f.length() - 1).split("],\\["))
                        .map(
                                str -> Arrays.stream(str.split(","))
                                        .map(Integer::parseInt)
                                        .toArray(Integer[]::new))
                        .toArray(Integer[][]::new);

        String s = "[5,4,3,2]";
        List<Integer> connects =
                s.length() == 2
                        ? new LinkedList<>()
                        : Arrays.stream(s.substring(1, s.length() - 1).split(","))
                        .map(Integer::parseInt)
                        .collect(Collectors.toList());

        System.out.println(getResult(ranges, connects));
    }

    public static int getResult(Integer[][] ranges, List<Integer> connects) {
        List<Integer[]> mergeList = Arrays.stream(ranges)
                .sorted((a, b) -> a[0] - b[0])
                .collect(Collectors.toList());

        outer:
        while (true) {

            int m = mergeList.size();
            for (int i = 0; i < m - 1; i++) {

                for (int j = i + 1; j < m; j++) {

                    Integer[] cur = mergeList.get(i);
                    Integer[] post = mergeList.get(j);
                    if (canUnion(cur, post)) {
                        cur[1] = Math.max(cur[1], post[1]);
                        mergeList.remove(j);
                        continue outer;
                    } else {
                        continue; // 剪枝
                    }
                }
            }
            break;
        }

        Collections.sort(mergeList, (a, b) -> a[0] - b[0]);
        LinkedList<Integer> diffs = new LinkedList<>();
        for (int i = 0; i < mergeList.size() - 1; i++) {
            diffs.add(mergeList.get(i + 1)[0] - mergeList.get(i)[1]);
        }
        Collections.sort(diffs, (a, b) -> b - a);
        Collections.sort(connects, (a, b) -> b - a);

        while (connects.size() > 0 && diffs.size() > 0) {
            if (connects.remove(connects.size() - 1) >= diffs.getLast()) { // 贪心
                diffs.removeLast();
            }
        }

        return diffs.size() + 1;
    }

    public static boolean canUnion(Integer[] cur, Integer[] post) {
        if (post[0] <= cur[1]) { // 已经提前排序combine了，cur左边界永远 <= post左边界
            return true;
        }
        return false;
    }
}